//在一个有向图中，节点分别标记为 0, 1, ..., n-1。图中每条边为红色或者蓝色，且存在自环或平行边。 
//
// red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地，blue_edges 中的每一个 [i, j] 对表示从
//节点 i 到节点 j 的蓝色有向边。 
//
// 返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，
//那么 answer[x] = -1。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
//输出：[0,1,-1]
// 
//
// 示例 2： 
//
// 
//输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
//输出：[0,1,-1]
// 
//
// 示例 3： 
//
// 
//输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
//输出：[0,-1,-1]
// 
//
// 示例 4： 
//
// 
//输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
//输出：[0,1,2]
// 
//
// 示例 5： 
//
// 
//输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
//输出：[0,1,1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 100 
// red_edges.length <= 400 
// blue_edges.length <= 400 
// red_edges[i].length == blue_edges[i].length == 2 
// 0 <= red_edges[i][j], blue_edges[i][j] < n 
// 
// Related Topics广度优先搜索 | 图 
//
// 👍 115, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import com.sun.javaws.jnl.RContentDesc;
import javafx.util.Pair;

import java.util.*;

class ShortestPathWithAlternatingColors {
    public static void main(String[] args) {
        Solution solution = new ShortestPathWithAlternatingColors().new Solution();
        solution.shortestAlternatingPaths(3, new int[][]{{0, 1}, {1, 2}}, new int[][]{});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // https://leetcode.cn/problems/shortest-path-with-alternating-colors/solution/java-by-wuzhenyu-pn8k/
        // DFS
        /*List<Integer>[] rlist, blist;
        int[] rStep, bStep; // 从0到节点i，颜色交替的情况下，最后一条边是红色或者蓝色的步数

        public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
            // true：表示红色 false：表示蓝色
            rlist = new ArrayList[n];
            blist = new ArrayList[n];
            rStep = new int[n];
            bStep = new int[n];
            for (int i = 0; i < n; ++i) {
                rlist[i] = new ArrayList<Integer>();
                blist[i] = new ArrayList<Integer>();
            }
            for (int i = 1; i < n; ++i) rStep[i] = bStep[i] = Integer.MAX_VALUE;
            for (int[] edge : redEdges) rlist[edge[0]].add(edge[1]);
            for (int[] edge : blueEdges) blist[edge[0]].add(edge[1]);
            // 从0开始，蓝色色边开始
            dfs(0, 0, false);
            // 从0开始，红色边开始
            dfs(0, 0, true);

            int[] res = new int[n];
            for (int i = 1; i < n; i++) {
                int step = Math.min(bStep[i], rStep[i]);
                if (step != Integer.MAX_VALUE) res[i] = step;
                    // 如果没有路径到达
                else res[i] = -1;
            }

            return res;
        }

        // flag : ture 当前该遍历红色边, false 相反
        public void dfs(int x, int step, boolean flag) {
            if (flag) {
                // 遍历红色边
                for (Integer next : rlist[x]) {
                    // 当前为红色
                    // 剪枝：如果之前搜索的步骤更小，那么就不用再搜索
                    if (rStep[next] <= step + 1) continue;
                    rStep[next] = step + 1;
                    // 找下一条蓝色边
                    dfs(next, step + 1, false);
                }
            } else {
                // 遍历蓝色边
                for (Integer next : blist[x]) {
                    // 当前为红色
                    // 剪枝：如果之前搜索的步骤更小，那么就不用再搜索
                    if (bStep[next] <= step + 1) continue;
                    bStep[next] = step + 1;
                    // 找下一条蓝色边
                    dfs(next, step + 1, true);
                }
            }
        }*/

        // BFS
        // 初始0可以走红色和蓝色两条路
        // 注意，因为有红蓝两种选择，则应该有两种标记（redVisited,blueVisited）
        public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
            List<Integer>[] rlist = new ArrayList[n], blist = new ArrayList[n];
            for (int i = 0; i < n; ++i) {
                rlist[i] = new ArrayList<Integer>();
                blist[i] = new ArrayList<Integer>();
            }
            for (int[] edge : redEdges) rlist[edge[0]].add(edge[1]);
            for (int[] edge : blueEdges) blist[edge[0]].add(edge[1]);
            boolean[] rVisited = new boolean[n];
            boolean[] bVisited = new boolean[n];
            int[] res = new int[n];
            Arrays.fill(res, -1);
            // int[]{cur, color, step}
            // 0：红色 1：蓝色
            Queue<int[]> queue = new LinkedList<>();
            // 初始0可以走红色和蓝色两条路
            queue.offer(new int[]{0, 0, 0});
            queue.offer(new int[]{0, 1, 0});
            while (!queue.isEmpty()) {
                int[] poll = queue.poll();
                int cur = poll[0], color = poll[1], step = poll[2];
                // 第一次遍历到的时候，就是步数最小的，更新步数
                if (res[cur] == -1) {
                    res[cur] = step;
                }

                // 如果为红色
                if (color == 0) {
                    for (Integer next : rlist[cur]) {
                        if (!rVisited[next]) {
                            rVisited[next] = true;
                            queue.offer(new int[]{next, 1, step + 1});
                        }
                    }
                } else {
                    for (Integer next : blist[cur]) {
                        if (!bVisited[next]) {
                            bVisited[next] = true;
                            queue.offer(new int[]{next, 0, step + 1});
                        }
                    }
                }
            }

            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
